import java.util.Stack;

public class QueueTest {
    /**
     * 栈匹配问题，
     * + 判断第二个输入序列是否可以是第一个输入序列的出栈结果。
     * + 示例1：
     *   第一个队列:[1,2,3,4.5]第二个队列:[4,5,3,2,1]
     *   输出结果:true
     *   但是需要注意：
     *   1，2，3，4，5
     *  4，5，3，2，1，6 ---false
     *
     *  1，2，3，4，5
     *  4，5，1 ---true
     *
     *  上述的两种情况：
     */

    public static boolean isPopOrder(int[] pPush,int[] pPop){
        if(pPush==null||pPop==null) {//压栈序列和弹出序列皆为空，则返回false
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i=0;
        int j=0;
        while(j < pPush.length) {
            if(pPop.length > pPush.length) {
                return false;
            }
            if(i < pPush.length) {
                stack.push(pPush[i]);//依次压入压栈序列中的元素
                i++;
            }
            if(stack.peek() == pPop[j]) {//栈顶元素与弹出序列中的元素进行比较
                stack.pop();//如果相等则弹出
                j++;
            }
            if (j == pPop.length) {//如果弹出序列中的元素全部比完，则该序列为弹出序列
                return true;
            }

            if(i == pPush.length && stack.peek() != pPop[j]) {//如果压栈序列已经全部压入栈中，但栈顶元素与弹出序列中的元素不相同
                //该序列不是弹出序列
                return false;
            }

        }
        return false;
    }
    public static void main(String[] args) {
        int[] arr={6, 1, 2, 3, 4, 5};
        int[] brr= {4, 5, 3, 2, 1};
        int[] crr= {1, 2, 3, 4, 5};
        int[] drr= {5, 4, 1, 2, 3};
        int[] frr= {4, 5, 3, 2, 1, 6};
        int[] err= {4, 5, 1};


//        System.out.println( isPopOrder(arr,brr));
//        System.out.println( isPopOrder(arr,crr));
        ///////
        System.out.println( isPopOrder(crr, err));
        ///////
//        System.out.println( isPopOrder(arr,drr));
//        System.out.println( isPopOrder(crr, frr));

    }
}
